package sort;
//1.4 希尔排序
//        分类 算法
//        希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本
//希尔排序是基于插入排序的以下两点性质而提出改进方法的：
//
//        插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
//        但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
//        希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
//        待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
//

public class XiErSort {
    public int[] sortArray(int[] nums) {
        int length = nums.length;
//        int step;
        for (int step = length/2; step >=1 ; step=step/2) {
            for (int i = step; i <length ; i++) {
//第一遍我这样写的  不行  不能在固定间隔组成的序列上排成有序的

//                if (nums[i]<nums[i-step]){
//                    int tmp=nums[i];
//                    nums[i]=nums[i-step];
//                    nums[i-step]=tmp;
//
//                }
//TODO:需要背代码了  写的很绝    就是插入排序  这一个for循环里面主要做两件事
// 依次对step间隔组成的序列排序 每添加一个step间隔的
// 元素 对前面已经排序好的元素进行插入排序
                int tmp=nums[i];
                int j=i-step;
                while (j>=0&&nums[j]>tmp){
                    nums[j+step]=nums[j];
                    j-=step;
                }
                nums[j+step]=tmp;

            }
        }



        return  nums;
    }

    public static void main(String[] args) {
        XiErSort xiErSort = new XiErSort();
        int[] ints = xiErSort.sortArray(new int[]{5, 3, 4, 6,8,3,6,4,5,9,2,4});
        for (int a:ints
             ) {
            System.out.println(a);

        }

    }

}
